package br.unicamp.integralization.bab;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

import br.unicamp.integralization.dto.Allocation;
import br.unicamp.integralization.dto.History;
import br.unicamp.integralization.dto.Subject;
import br.unicamp.integralization.dto.SubjectGroup;

public class BranchAndBound {

	public static Allocation execute(History originalHistory) throws Exception {
		SolutionNode current = null;
		PriorityQueue<SolutionNode> queue = new PriorityQueue<SolutionNode>(
				1000, new Comparator<SolutionNode>() {

					@Override
					public int compare(SolutionNode lhs, SolutionNode rhs) {
						return lhs.getLowerBound() - rhs.getLowerBound();
					}
				});

		current = new SolutionNode();
		// Matérias obrigatorias que ja foram feitas são
		// retornadas pela função.
		History clonedHistory = originalHistory.clone();
		List<Subject> mandatorySubjects = current.initialize(clonedHistory);
		queue.add(current);
		int U = Integer.MAX_VALUE;

		int droppedOut = 0;

		while (queue.isEmpty() == false) {
			current = queue.poll();

			// Se temos uma solução, ela é a melhor de todas.
			if (current.isSolution(clonedHistory)) {
				System.out.println("Foram jogados fora " + droppedOut);
				;
				return current.createAllocation(clonedHistory,
						mandatorySubjects);
			}

			// Geramos os filhos do próximo nível, responsáveis por alocar
			// a matéria de indice subjectIndex+1.
			// subjectIndex se refere ao índice em que a matéria em questão se
			// encontra
			// na lista de disciplinas cursadas no historico do aluno

			for (SolutionNode solutionNode : current
					.generateChilds(clonedHistory)) {

				if (solutionNode.getLowerBound() <= U) {
					U = Math.min(solutionNode.getUpperBound(), U);
					queue.add(solutionNode);
				} else {
					droppedOut++;
				}
			}
		}

		throw new Exception(
				"Não foi encontrada nenhuma solução para a Integralização");

	}

	public static Allocation diff(Allocation catalog, Allocation best) {
		Allocation alloc = catalog.clone();

		for (Subject subject : best.getMandatorySubjects().getSubjects()) {
			alloc.getMandatorySubjects().removeSubject(subject);
		}

		for (int i = 0; i < best.getElectiveGroups().size() - 1; i++) {
			List<Subject> subjects = best.getElectiveGroups().get(i)
					.getSubjects();
			SubjectGroup subjectGroup = alloc.getElectiveGroups().get(i);
			for (int j = 0; j < subjects.size(); j++) {
				Subject subject = subjects.get(j);
				subjectGroup.removeSubject(subject);
			}
		}

		for (int i = 0; i < best.getElectiveGroups().size() - 1; i++) {
			SubjectGroup bestSubjectGroup = best.getElectiveGroups().get(i);
			SubjectGroup catalogSubjectGroup = catalog.getElectiveGroups().get(
					i);
			SubjectGroup allocSubjectGroup = alloc.getElectiveGroups().get(i);
			allocSubjectGroup.setCredits(catalogSubjectGroup.getCredits()
					- bestSubjectGroup.getCredits());
		}

		return alloc;
	}

}
